CS1.406 Advanced Algorithms (Spring 2024)

---

Announcements

• Teaching assistants: Nithish Raja, Vidit Jain
• Schedule: Tuesday and Friday, 14:00 – 15:30
• Classroom: H104

Topics

1. Introduction to Polynomial Identity Testing, Univariate Interpolation, Verifying Matrix Multiplication

   • References: Section 7.2 & 7.3 of [1], and Section 1.1 & 1.3 of [2].

2. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

   • References: Section 12.4 of [1], Section Moshkovitz’s alternate proof of DLSZ lemma, and Mulmuley-Vazirani-Vazirani ‘87

3. Randomized routing

   • References: Section 4.2 of [1], Section 4.5.1 of [2], Lovett’s course notes from UCSD, and J R Lee’s course notes from UWash.

4. MaxSAT, MaxCUT, Derandomization with conditional probabilities

   • References: Section 6.2 and 6.3 of [2].

5. Min-Cut, and Las Vegas & Monte carlo

   • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

6. Approximate Counting & Approximate Sampling

   • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].

7. Random walks and Markov chains

   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

8. Markov Chains – 2SAT

   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

9. Markov Chains – 3SAT

   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

10. Concentration bounds

    • References: Chapter 4 of [2].

11. Chernoff bound, Error reduction, Set balancing

    • References: Chapter 4 of [2].

References

1. R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
2. M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
3. N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.

Similar courses

1. Previous offering of the course - Spring 2022
2. See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).